#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int solution(int m, std::string s) {
    int n = s.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, -1));
    dp[0][0] = 0;

    // 第一次动态规划，计算从每个字符开始，为了匹配 "UCC" 产生的最小编辑距离和匹配成功时的长度
    std::vector<std::vector<std::pair<int, int>>> match_info(n);  // match_info[i] = 从s[i]开始，匹配“UCC”的(最小编辑距离，匹配成功时的长度)
    for (int i = 0; i < n; ++i) {
        int max_len = std::min(n - i, 3 + m);  // 从当前字符s[i]开始，匹配成功时可能达到的最大长度
        // 从当前字符s[i]开始，匹配 "UCC" 的最小编辑距离
        std::vector<std::vector<int>> dp_match(4, std::vector<int>(max_len + 1, 999999999));
        dp_match[0][0] = 0;
        for (int p = 0; p < 4; ++p) {  // 从s[i]开始匹配"UCC" 的进度：‘’->‘U'->'UC'->'UCC’
            for (int q = 0; q <= max_len; ++q) {  // 匹配过程中划过的长度 = 0,1,...,max_len
                if (dp_match[p][q] > m)  // 编辑次数用完了
                    continue;
                if (p < 3 && q < max_len) {  // 保留/替换
                    int cost = (s[i + q] == "UCC"[p]) ? 0 : 1;
                    dp_match[p + 1][q + 1] = std::min(dp_match[p + 1][q + 1], dp_match[p][q] + cost);
                }
                if (p < 3) {  // 插入
                    dp_match[p + 1][q] = std::min(dp_match[p + 1][q], dp_match[p][q] + 1);
                }
                if (q < max_len) {  // 删除
                    dp_match[p][q + 1] = std::min(dp_match[p][q + 1], dp_match[p][q] + 1);
                }
            }
        }
        // 统计
        for (int q = 0; q <= max_len; ++q) {
            int c = dp_match[3][q];
            match_info[i].push_back({c, q});  // (编辑距离，匹配长度)
        }
    }

    // 主过程的动态规划：
    for (int i = 0; i <= n; ++i) {
        for (int e = 0; e <= m; ++e) {
            if (dp[i][e] == -1)
                continue;
            if (i < n) {  // 不尝试匹配 "UCC" --> 直接跳过/删除当前字符
                dp[i + 1][e] = std::max(dp[i + 1][e], dp[i][e]);  // 保留
                if (e + 1 <= m) {  // 删除
                    dp[i + 1][e + 1] = std::max(dp[i + 1][e + 1], dp[i][e]);
                }
            }
            if (i < n && !match_info[i].empty()) {  // 尝试匹配
                for (auto& [c, l] : match_info[i]) {  // 从当前字符串开始匹配‘UCC’的(最小编辑距离，匹配成功时长度)
                    if (e + c <= m && i + l <= n) {
                        dp[i + l][e + c] = std::max(dp[i + l][e + c], dp[i][e] + 1);
                    }
                }
            }
        }
    }

    // 找到最大匹配数量
    int max_substrings = 0;
    for (int e = 0; e <= m; ++e) {
        max_substrings = std::max(max_substrings, dp[n][e]);
    }
    return max_substrings;
}

int main() {
    std::cout << (solution(3, "UCUUCCCCC") == 3) << std::endl;
    std::cout << (solution(6, "U") == 2) << std::endl;
    std::cout << (solution(2, "UCCUUU") == 2) << std::endl;
    return 0;
}
